#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "algorithm"

using namespace std;

/*
 *给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:
输入: s = "aab"
输出: "aba"
示例 2:

输入: s = "aaab"
输出: ""
 *
 *
 * todo 这个题是抄的 自己写的不对
 *
 *  有一个条件如果字符 长度+1 /2 >出现最大次数 就不行
 *
 *  1 先根据频率排序
 *  2 先插入奇数 后插入偶数 因为奇数>=偶数 2*max_fre-1>s.size()
 *
 * */


string reorganizeString(string s) {
    unordered_map<int, int> mp;
    int max_fre;
    for (int i = 0; i < s.size(); ++i) {
        ++mp[s[i]];
        max_fre = max(max_fre, mp[s[i]]);
    }


    //注意这个条件
    if (2 * max_fre - 1 > s.size())
        return "";

    vector<std::pair<int, int> > res(mp.begin(), mp.end());
    sort(res.begin(), res.end(), [&](pair<int, int> &a, pair<int, int> &b) {
        //根据频率从大到小排序
        return a.second > b.second;
    });

    int index = 0;//从奇数位置开始填充

    for (int i = 0; i < res.size(); ++i) {

        while (res[i].second > 0) {
            s[index] = res[i].first;
            index += 2;
            --res[i].second;
            if (index >= s.size())
                index = 1;
        }


    }

    return s;


}